package BinaryTree;

/**
 * 查找一个节点中序遍历时后面的那个节点
 *
 * @author Liaorun
 */
public class SuccessorNode {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;


        public Node(int value) {
            this.value = value;
        }
    }


    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return node;
        }

        if (node.right != null) {
            // 当前节点有右子节点

            // 则后继节点为 右树的最左节点
            return getLeftMost(node.right);
        } else {
            // 当前节点无右子节点

            Node parent = node.parent;

            // 父节点为空 && 当前节点是其父亲节点的左孩子
            // parent == null 的触发条件为 node 是中序遍历的结果中最后一个节点
            // 否则都能找到一个节点是其父节点的左节点的情况，然后就提前跳出循环，不会走到根节点在跳出
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }

            return parent;
        }
    }

    /**
     * 获取一颗树的最左节点
     *
     * @param node 头节点
     * @return 树的最左节点 or null
     */
    private static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }

        // 一直向左节点走，走到叶节点为止
        while (node.left != null) {
            node = node.left;
        }

        return node;
    }
}
